'''
递归过程：
1、写出临界条件
2、找这一次和上一次的关系
3、调用函数自身计算
'''


# n阶楼梯，每次上1个台阶或者2个台阶，问一共有多少种走法
# f(n+1) = f(n) + f(n-1)
# f(n) = f(n-1) + f(n-2)
# ...
# f(3) = f(2) + f(1)
# f(2) = 2
# f(1) = 1
def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    return f(n - 1) + f(n - 2)

# for i in range(11):
#     print("楼梯有%d阶的时候，总共有%d种走法" % (i, f(i)))


a = [0, 1, 2]
for i in range(3, 11):
    a.append(a[i - 1] + a[i - 2])
    print("楼梯有%d阶的时候，总共有%d种走法" % (i, a[i]))
